/*
 * Na šachovnici P (obdelnikovou sit m * k) je pevně rozmístěno f bodů.
 * Úkolem je rozmístit dalších b-f bodů, tak aby byl maximální součet matice
 * Euklidovských vzdáleností všech dvojic bodů = sum_i_j d(i,j). Body se nesmějí
 * překrývat.
 *
 * Geometrická interpretace: rozmístit na ploše b bodů tak, aby byly co nejdál
 * od sebe.
 */

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include "main.h"
#include "io.h"
#include "state.h"
#include "stack.h"
#include "plane.h"
#include "util.h"

#define INPUT_FILE_PATH "./input.txt"
#define CHECK_STATUS_INTERVAL 500
#define DEBUG 0

void doWork(void);
void processState(Stack *, State *state, State **, double *);
void generateChildren(Stack *s, State *state);


/* unsigned long long int je zoufale málo pro tyto potřeby */

/* unsigned long long int combinations;
 unsigned long long int progress = 0;
 int percents = 0; */

/*
 * Hlavní funkce programu.
 */
int main(int argc, char **argv) {
	/* nulové buffery pro výstup --> pro ladění při segfaultech */
	setvbuf(stdout, NULL, _IONBF, 0);
	setvbuf(stderr, NULL, _IONBF, 0);

	char *filename;
	if (argv[1]){
	
	filename=argv[1];	

	} else filename=INPUT_FILE_PATH;

	if (argv[2]) {
		proc_num=atoi(argv[2]);
		if (proc_num) {
		/*	
			if (proc_num>omp_get_num_procs()) {
					fprintf(stderr, "Number of demanded threads is too big. Maximum threads =  %d\n", omp_get_num_procs() );
					return EXIT_FAILURE;
			}
*/
		} else proc_num = omp_get_num_procs();
	
	} else proc_num = omp_get_num_procs();
	
	printf("Vítejte v programu nenávist!\n");

	/* otevřeme soubor se vstupními daty */
	FILE *inputFile = fopen(filename, "r");
	if(inputFile == NULL){
		fprintf(stderr, "ERROR READING INPUT FILE %s\n", INPUT_FILE_PATH);
		return EXIT_FAILURE;
	}

	/* načteme vstupní data */
	loadInput(inputFile);

	/* validace vstupních dat */
	if(b > m * k){
		fprintf(stderr, "Je specifikováno více bodů, než se na plán může vejít (%d > %d*%d)\n", b, m, k);
		return EXIT_FAILURE;
	}
	if(b < f){
		fprintf(
				stderr,
				"Počet pevně umístěných bodů je větší než celkový počet bodů: (b < f, %d < %d). Nelze umístit záporný počet bodů.\n",
				b, f);
		return EXIT_FAILURE;
	}
	int i;
	for(i = 0; i < f; i++){
		if(fixedPoints[i].x >= m || fixedPoints[i].y >= k){
			fprintf(stderr, "Jedna souřadnice je specifikována mimo plán ([%d, %d])\n", fixedPoints[i].x,
					fixedPoints[i].y);
			return EXIT_FAILURE;
		}
	}

	/* int N = m*k - f, K = b - f;
	 combinations = fact(N)/(fact(K)*fact(N - K)); */

	/* výpis vstupních dat */
	printf("Vstupní data: m = %d, k = %d, f = %d, b = %d.\n", m, k, f, b);
	for(i = 0; i < f; i++){
		printf("%d: [%d,%d] ", i, fixedPoints[i].x, fixedPoints[i].y);
	}
	printf("\n");
	/* printf("Počet kombinací: %d", combinations); */

	printf("Pocet procesoru k dispozici: %d\n", proc_num);

	loadbalancer = stackInit();
	initstack = stackInit();

	/* Zadání počátečního stavu */
	stackPush(initstack, allocateState(0));

	/* Spuštění práce */
	doWork();

	return 0;
}

/*
 * Pracovní metoda programu s hlavním cyklem, který má na zodpovědnost zpracovat
 * všechny stavy. Po skončení vypíše nejlepší řešení.
 */
void doWork(void){
    

    State *state,*tmp;
    double start,end;
    int everyone_works=proc_num;
    int workers=everyone_works;
    int final=0,loop,init=1;

 /* Nejlepší dosavadní řešení */

    State *globalBestState;
    double globalBestValue=0;

    omp_init_lock(&lock);
    omp_init_lock(&initlock);
    omp_init_lock(&loadcontrol);
    omp_init_lock(&bestlock);
    omp_init_lock(&noworklock);
    omp_set_lock(&noworklock);
    start=omp_get_wtime();
    generateChildren(initstack,stackPop(initstack));

    int can_take=(int)stackSize(initstack)/proc_num;
    !can_take?can_take=1:can_take;
    if(DEBUG) printf("Work division. coef: %d\n",can_take);
    
    
    // nastavuji pocet vlaken    
    omp_set_num_threads(proc_num);
	

    // Zacatek paralelni sekce
    //
    #pragma omp parallel default(shared) \
    firstprivate(can_take,init) private(lostack,state,tmp) \
    shared(loadbalancer,initstack,b,f,k,m,fixedPoints,globalBestState,globalBestValue) 
    {
    	State *bestState=NULL;
    	double bestValue = -1;
	

        
        if(DEBUG) printf("IDPROC: %d >> I'm alive.\n",omp_get_thread_num());
        
        lostack = stackInit();
        while(1){
            
            
            for (loop=0; loop<CHECK_STATUS_INTERVAL; loop++){
                
                if (!stackSize(lostack) && stackSize(initstack)){
                    // inicializace z init stacku
		    if (init){
                    omp_set_lock(&initlock);
                    while(can_take--) { if(stackSize(initstack)) stackPush(lostack,stackPop(initstack)); else break; }
		    init = 0;
                    omp_unset_lock(&initlock);

		} else{

			omp_set_lock(&initlock);
			if(stackSize(initstack)) stackPush(lostack,stackPop(initstack));
		   	omp_unset_lock(&initlock);
		}
			
			// tady nam to bude obcas delit nulou :) :) ... asi vazne budu muset pouzit mutex
			int count=(int)(stackSize(loadbalancer))/(everyone_works-workers);
			if(DEBUG) printf("IDPROC: %d >> FULL Count: %d\n",omp_get_thread_num(),count);
			count<1?count=1:count;

                }
		
		if (!stackSize(lostack)) break;
                    
                    state=stackPop(lostack);
                    processState(lostack, state, &bestState, &bestValue);
                
            }
	         //printf("IDPROC: %d >> Loadbalance: %d, Final: %d Everyoneworks: %d \n", omp_get_thread_num(), loadbalance, final, everyone_works);
	if ( ! stackSize(lostack) ) {
        
		// delim svoji praci na loadbalancer
		omp_set_lock(&lock);
		if (stackSize(loadbalancer))
		{
			 int count=(int)(stackSize(loadbalancer))/(everyone_works);
			 count<1?count=1:count;
			 while(count--) {
				tmp = stackPop(loadbalancer);
				if(!tmp) {
				   if(DEBUG) printf("IDPROC: %d >> POKUS O NACTENI PRAZDNEHO STAVU!!!!\n",omp_get_thread_num());
				} else { stackPush( lostack,tmp);}}
			if (stackSize(loadbalancer) > 0) omp_unset_lock(&noworklock);
			 omp_unset_lock(&lock);
			 continue;
		}
		omp_unset_lock(&lock);


//kriticka sekce I - promena workers !! 
               omp_set_lock(&loadcontrol); 
                if(DEBUG) printf("IDPROC: %d >> Need some stuff. Workers: %d \n",omp_get_thread_num(),workers);
               // #pragma omp atomic
                workers--;

                if (!workers) {
                    
                    if(DEBUG)printf("IDPROC: %d >> FINITO.\n",omp_get_thread_num());
                    #pragma omp atomic
                    final++;
		// probouzim dalsi vlakno
                    omp_unset_lock(&noworklock);
		//konec kriticke sekce I
               	    omp_unset_lock(&loadcontrol); 
                    break;
                    
                }

//konec kriticke sekce I - promena workers !!
               omp_unset_lock(&loadcontrol); 
                
               if(DEBUG) printf("IDPROC: %d >> Going to bed. Workers: %d \n",omp_get_thread_num(),workers);

//  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! uspani vlakna !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
               omp_set_lock(&noworklock);
//  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! uspani vlakna !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

               omp_set_lock(&loadcontrol); 
                //#pragma omp atomic
               workers++;

                if(DEBUG) printf("IDPROC: %d >> Wakeing up. Stack size: %d, Idle: %d, Workers: %d \n"
                					,omp_get_thread_num(), stackSize(loadbalancer), everyone_works-workers, workers);
               omp_unset_lock(&loadcontrol); 

                
                if(final && !stackSize(lostack)) {
                    omp_unset_lock(&noworklock ); 
		    //omp_unset_lock(&loadcontrol);
		    break;
                } else if (final && stackSize(lostack)) continue;
                
                continue;

            }

            else {


                    if(final && !stackSize(lostack)) {
                        omp_unset_lock( &noworklock ); break;
                    } else if (final && stackSize(lostack)) continue;

                
                if (omp_test_lock(&loadcontrol)){
                    if (everyone_works-workers) {
                    if (stackSize(lostack) > everyone_works-workers){
                        
                        if(DEBUG) printf("IDPROC: %d >> FULL Load some stuff on gl. stack. Count: %d\n",omp_get_thread_num(),everyone_works-workers);
			
			// tady nam to bude obcas delit nulou :) :) ... asi vazne budu muset pouzit mutex
			int count=(int)(stackSize(lostack))/(everyone_works-workers);
			if(DEBUG) printf("IDPROC: %d >> FULL Count: %d\n",omp_get_thread_num(),count);
			count<1?count=1:count;

                        omp_set_lock(&lock);
                        while(count--) {
			tmp=stackPop(lostack);
			if (!tmp){
                	if(DEBUG) printf("IDPROC: %d >> POKUS O NACTENI PRAZDNEHO STAVU Z LOKALU!!!!\n",omp_get_thread_num());}
                	else {
                            stackPush( loadbalancer,tmp);
                        }
		}
                        omp_unset_lock(&lock);
		       	// probudim jedno hladove vlakno
                        omp_unset_lock(&noworklock);
                        omp_unset_lock(&loadcontrol);
                        continue;
                        
                    }
                    else {
			omp_set_lock(&lock);
		    	int count=stackSize(lostack);
			while(count--) {
			tmp=stackPop(lostack);
                        if (!tmp){
                        if(DEBUG) printf("IDPROC: %d >> POKUS O NACTENI PRAZDNEHO STAVU Z LOKALU!!!!\n",omp_get_thread_num());}
                        else {
                            stackPush( loadbalancer,tmp);
			}}
			omp_unset_lock(&lock);
			omp_unset_lock(&loadcontrol);
                        if(DEBUG) printf("IDPROC: %d >> PART: Load some stuff on gl. stack. Count: %d\n",omp_get_thread_num(),everyone_works-workers);
                        continue;
                        
                    }
                    
                    
                }
                    omp_unset_lock(&loadcontrol);
	}
                
                
            }
            
            
        }
       
	omp_set_lock(&bestlock);
	if (bestValue > globalBestValue) {
		globalBestValue=bestValue;
		globalBestState=bestState;
        printf("IDPROC: %d >>; Replacing bestValue: %f \n", omp_get_thread_num(), globalBestValue);}
	omp_unset_lock(&bestlock);
        printf("IDPROC: %d >>; Exiting! Time: %f \n", omp_get_thread_num(),omp_get_wtime()-start);

    }
    end=omp_get_wtime();
    omp_destroy_lock(&lock);
    omp_destroy_lock(&initlock);
    omp_destroy_lock(&loadcontrol);
    omp_destroy_lock(&bestlock);
    omp_destroy_lock(&noworklock);

    printf("BEST SOLUTION:\n");
    printPlane(globalBestState);
    printf("Solution value: %f\n", globalBestValue);
    printf("thc:%d Duration: %f\n",proc_num,end-start);
    
    
}


/*
 * Metoda zpracuje stav - buď spočítá jeho hodnotu (pro konečné stavy) nebo
 * vygeneruje potomky.
 */
void processState(Stack *lostack, State *state, State** bestState, double *bestValue) {

	/* Pro stavy na konečné hloubce - listy */
	if(state->depth == b - f){
		double result = evaluateState(state);
		if(result > *bestValue){
		*bestValue = result;
		*bestState = state;
		}
		else{
			freeState(state);
		}
	}
	/* Pro stavy ve stromu - větve */
	else{
		generateChildren(lostack, state);
		freeState(state);
	}
}

/*
 * Pro zadaný stav vygeneruje potomky a vloží je do stacku.
 */
void generateChildren(Stack *s, State *state) {

	/*
	 * Optimalizace --> z permutací na kombinace.
	 */
	int lastPointX = 0, lastPointY = 0;
	int i;
	for(i = 0; i < state->depth; i++){
		if(lastPointX < state->statePoints[i].x){
			lastPointX = state->statePoints[i].x;
			lastPointY = state->statePoints[i].y;
		}
		else if(lastPointX == state->statePoints[i].x){
			lastPointY = max(lastPointY, state->statePoints[i].y);
		}
	}
	/*
	 * hasPoint - proměnná, která určuje, zda-li je na aktuálních souřadnicích
	 * už bod umístěn (buď fixní nebo umístěný).
	 */
	int j, l, hasPoint;
	for(i = lastPointX; i < m; i++){
		for(j = 0; j < k; j++){
			if(j == 0 && i == lastPointX){
				j = lastPointY;
			}
			hasPoint = 0;

			/* prohledáváme fixní body */
			for(l = 0; l < f; l++){
				if(fixedPoints[l].x == i && fixedPoints[l].y == j){
					hasPoint = 1;
					break;
				}
			}
			if(hasPoint){
				continue;
			}

			/* prohledáváme již umístěné body */
			for(l = 0; l < state->depth; l++){
				if(state->statePoints[l].x == i && state->statePoints[l].y == j){
					hasPoint = 1;
					break;
				}
			}
			if(hasPoint){
				continue;
			}

			State *newState = childState(state);
			newState->statePoints[state->depth].x = i;
			newState->statePoints[state->depth].y = j;
			stackPush(s, newState);
			//		printf("IDPROC: %d >> Stack size: %d \n", omp_get_thread_num(),stackSize(s));
		}
	}

}
